package main.java.algorithms;

import main.java.utils.SortTestHelper;

import java.util.Random;

/**
 * @author Wrb
 * @date 2019/5/27 11:39
 */
public class QuickSort implements Sort {
	@Override
	public void sort(int[] arr, int n) {
		sort(arr, 0, n - 1);
	}

	//递归进行快排
	private void sort(int[] arr, int l, int r) {

		//优化1 当数组小到一定程度，插入排序比归并排序快，此时调用插入排序
		if (r - l <= 20) {
			InsertionSort.sort(arr, l, r);
			return;
		}

		int p = partition(arr, l, r);
		sort(arr, l, p - 1);
		sort(arr, p + 1, r);
	}

	//对数组arr[l....r]部分进行partition操作
	//返回值p 即为元素所在位置 使得arr[l...p-1]<arr[p] ， arr[p+1...r]>arr[p]
	private int partition(int[] arr, int l, int r) {
		//优化2：随机选取基准
		SortTestHelper.swap(arr, l, new Random().nextInt(r - l + 1) + l);
		int v = arr[l];
		int j = l;
		for (int i = l + 1; i <= r; i++) {
			if (arr[i] < v) {
				SortTestHelper.swap(arr, ++j, i);
			}
		}
		SortTestHelper.swap(arr, l, j);
		return j;
	}
}
